#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int numRollsToTarget(int n, int k, int target) {
        vector<vector<int>> dp(n + 1, vector<int>(target + 1));
        int mod = 1e9 + 7;
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++)
            for (int t = 0; t <= target; t++)
                for (int z = 1; z <= k; z++)
                    dp[i][t] = (dp[i][t] + (t - z < 0 ? 0 : dp[i - 1][t - z])) % mod;
        return dp[n][target];
    }
};